package com.shawn.datastructure.array;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class MajorityElement {

	public int majorityElement(int[] nums) {
		int len = nums.length;
		int result = 0;
		Map<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < len; i++) {
			Integer count = map.get(nums[i]);
			if (count == null) {
				count = 1;
			} else {
				count++;
			}
			map.put(nums[i], count);
			if (count > len / 2) {
				result = nums[i];
				break;
			}
		}
		return result;
	}

	// Sorting
	public int majorityElement1(int[] nums) {
		Arrays.sort(nums);
		return nums[nums.length / 2];
	}

	// Hashtable
	public int majorityElement2(int[] nums) {
		Map<Integer, Integer> myMap = new HashMap<Integer, Integer>();
		//Hashtable<Integer, Integer> myMap = new Hashtable<Integer, Integer>();
		int ret = 0;
		for (int num : nums) {
			if (!myMap.containsKey(num)) {
				myMap.put(num, 1);
			} else {
				myMap.put(num, myMap.get(num) + 1);
			}
			if (myMap.get(num) > nums.length / 2) {
				ret = num;
				break;
			}
		}
		return ret;
	}

	// Moore voting algorithm
	public int majorityElement3(int[] nums) {
		int count = 0, ret = 0;
		for (int num : nums) {
			if (count == 0) {
				ret = num;
			}
			if (num != ret) {
				count--;
			} else {
				count++;
			}
		}
		return ret;
	}

	// Bit manipulation
	public int majorityElement4(int[] nums) {
		int[] bit = new int[32];
		for (int num : nums) {
			for (int i = 0; i < 32; i++) {
				if ((num >> (31 - i) & 1) == 1) {
					bit[i]++;
				}
			}
		}
		int ret = 0;
		for (int i = 0; i < 32; i++) {
			bit[i] = bit[i] > nums.length / 2 ? 1 : 0;
			ret += bit[i] * (1 << (31 - i));
		}
		return ret;
	}

}
